翻訳と辞書 Words near each other ・ Parallel adoption ・ Parallel algorithm ・ Parallel and cross cousins ・ Parallel array ・ Parallel ATA ・ Parallel axis theorem ・ Parallel bars ・ Parallel Bus Interface ・ Parallel card ・ Parallel Cinema ・ Parallel college ・ Parallel College (film) ・ Parallel Colt ・ Parallel communication ・ Parallel compression ・ Parallel computation thesis ・ Parallel computing ・ Parallel constraint satisfaction processes ・ Parallel construction ・ Parallel coordinates ・ Parallel Creek ・ Parallel curve ・ Parallel database ・ Parallel Dimensions (album) ・ Parallel Dreams ・ Parallel education ・ Parallel Element Processing Ensemble ・ Parallel evolution ・ Parallel Extensions ・ Parallel fiber Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Parallel computation thesis ： ウィキペディア英語版 Parallel computation thesis In computational complexity theory, the parallel computation thesis is a hypothesis which states that the ''time'' used by a (reasonable) parallel machine is polynomially related to the ''space'' used by a sequential machine. The parallel computation thesis was set forth by Chandra and Stockmeyer in 1976. In other words, for a computational model which allows computations to branch and run in parallel without bound, a formal language which is decidable under the model using no more than $t(n)$ steps for inputs of length ''n'' is decidable by a non-branching machine using no more than $t(n)^k$ units of storage for some constant ''k''. Similarly, if a machine in the unbranching model decides a language using no more than $s(n)$ storage, a machine in the parallel model can decide the language in no more than $s(n)^k$ steps for some constant ''k''. The parallel computation thesis is not a rigorous formal statement, as it does not clearly define what constitutes an acceptable parallel model. A parallel machine must be sufficiently powerful to emulate the sequential machine in time polynomially related to the sequential space; compare Turing machine, non-deterministic Turing machine, and alternating Turing machine. N. Blum (1983) introduced a model for which the thesis does not hold. However, the model allows $2^$ or $2^\{T(n)^\{O(1)\}\}$, in defense of the thesis. Goldschlager (1982) proposed a model which is sufficiently universal to emulate all "reasonable" parallel models, which adheres to the thesis. Chandra and Stockmeyer originally formalized and proved results related to the thesis for deterministic and alternating Turing machines, which is where the thesis originated. == References == Category:Theory of computation 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Parallel computation thesis」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.